\section{Groups}

A group is a collection of objects with a predefined operation. For instance, the set of all the integers under addition is a well-known group. Every group must satisfy certain axioms that are summarized in the following definition. First a binary operation on a set $K$ in its most general form is defined as:
\[
.: K * K \rightarrow K
\]
Thus for $a,b \in K$ we write:
\[
.(a,b)=(a.b) \in K.
\]

It is customary to drop the '$.$' operator and show the operation as a "product", i.e. $(a.b) = ab$.

\begin{Def}
A non-empty set $G$ closed under a binary operation '$.$' is a group provided that the following are satisfied:\\
i) (associativity) For all $a,b,c \in G$, $a.(b.c)=(a.b).c$\\
ii) (identity) there exists $e \in G$, such that $a.e=e.a=a$ for every $a \in G$\\
iii) (inverse) for every $a \in G$, there exists $a^{-1} \in G$ such that $a.a^{-1}=a^{-1}.a=e$
\end{Def}

\begin{eg}
Group of all integer numbers under addition - $(\mathbb{Z},+)$, with zero as the identity and negative numbers as the inverse\\
\end{eg}

\begin{eg}
Group of positive, non-zero real numbers under multiplication - $(\mathbb{R}^{+},*)$, with $1$ as the identity and reciprocals as the inverse\\
\end{eg}
    
From the definition of a group the following properties immediately follow and can be proven:\\

\begin{Thrm}
The identity element is unique in a group.\\
\end{Thrm}
\begin{proof}
Let $e_{1},e_{2} \in G$ be two distinct identity elements in $G$, we have:\\
\[
e_{1} = e_{1}*e_{2} = e_{2}
\]
\end{proof}

\begin{Thrm}
Inverse is unique.\\
\end{Thrm}
\begin{proof}
Let $a_{1},a_{2} \in G$ be distinct inverses of $a \in G$, we have:\\
\[
a_{1}=a_{1}.a.a_{2}=a_{2}
\]
\end{proof}

\begin{Thrm}
If $a,b \in G$, then $(a.b)^{-1}=b^{-1}.a^{-1}$\\
\end{Thrm}

A special type of group is called an abelian group which is defined next.\\

\begin{Def}
A group $G$ is called {\bf abelian} if and only if for every $a,b \in G$, $a.b=b.a$
\end{Def}

In other words, if elements in a group commute, then the group is abelian. For instance, both $(\mathbb{Z},+)$ and $(\mathbb{R}^{+},*)$ defined previously are abelian. Just as any set can have a subset, it is natural to define a subgroup which we next seek to do.\\ 

\begin{Def}
A subset $H$ of a group $G$ is a {\bf subgroup} if and only if it is closed under the binary operation of $G$ and satisfies the axioms.
\end{Def} 

A subgroup $H$ of a group $G$ is denoted as $H < G$. To verify this relation, a convenient test, the {\bf one-step subgroup test}, is available as follows: for $H$ to be a subgroup of $G$, it suffices to show that for every $a,b \in H$, $ab^{-1}$ is also in $H$.

\begin{Thrm}
The intersection of two subgroups is a subgroup.
\end{Thrm}
\begin{proof}
We prove this result using the subgroup test. Let $H_{1},H_{2} < G$ and $a,b \in H_{1} \cap H_{2}$. Based on this and since $H_{1}$ and $H_{2}$ are subgroups themselves, $a,b,b^{-1}$ are in both subgroups and thus $ab^{-1}$ is in both, hence in their intersection.   
\end{proof}

\begin{Thrm}
The set of elements of $G$ that commute with an element $a \in G$ is a subgroup of $G$ called the {\bf Centralizer of g} and denoted by $G(a)=\{g \in G | ga=ag\}$.
\end{Thrm}
\begin{proof}
We prove this result using the subgroup test. Let $g_{1},g_{2} \in G$ such that they commute with $a$. We can write,
\[
g_{1}a=ag_{1} \Rightarrow g_{1}ag_{2}^{-1}=ag_{1}g_{2}^{-1} \Rightarrow g_{1}g_{2}^{-1}a=ag_{1}g_{2}^{-1}
\]
The last result follows due to the fact that if $g_{2}$ commutes with $a$, so does its inverse.
\end{proof} 

\begin{Thrm}
The set $Z(G)=\{a \in G | ag=ga,g \in G\}$ called the {\bf Center of a Group} is a subgroup.
\end{Thrm}
\begin{proof}
This set is the intersection of such sets as those in the previous theorem, and it is already shown that the intersection of subgroups is itself a subgroup.
\end{proof} 

\begin{Def}
$G$ is a {\bf cyclic group} with {\bf generator} $a$ if\\
$G = \{a^{n} ; n \in Z\}$
\end{Def}

\begin{Def}
A group $G$ has {\bf order} $n$ denoted by $|G|=O(G)$ if it has $n$ elements.
\end{Def}

\begin{Def}
The {\bf order of an element} $a \in G$ is the order of the cyclic subgroup generated by $a$.
\end{Def}
 
\begin{Thrm}
Any subgroup of a cyclic group is a cyclic group.\\
\end{Thrm}
\begin{proof}
Let $H < G$ where $G$ is a cyclic group. Let $a^{i} \in H$ have the least power of $a$ in subgroup $H$ and $a^{j}$ be any other element in $H$. Therefore $j = p*i + r$ for some $p,r \in Z$. It follows that,
\[
a^{j}=a^{p*i + r}=(a^{i})^{p}a^{r}
\]
multiplying both sides by the inverse, we have
\[
a^{j}(a^{i})^{-p}=a^{r}
\]
The right hand side is in $H$ since it is subgroup, and so has to be $a^{r}$. But we know $0 < r < p$ by division theorem. This implies that $r=0$ meaning that every element of $H$ is also a power of $a$.
\end{proof}

\begin{Thrm}
Let $G$ be a cyclic group with $n$ elements and $a \in G$. An element $b=a^{s} \in G$ generates a cyclic group with precisely $\frac{n}{d}$ elements where $d$ is the Greatests Common Divisor (gcd) of $n$ and $s$. 
\end{Thrm}
\begin{proof}
It is already shown that any subgroup of a cyclic group is cyclic itself. We need to show that the cyclic group containing $b$ has $\frac{n}{d}$ elements. We know $b^{k}=(a^{s})^{k}=e$ for some integer $k=|<b>|$. This implies that $n$ must divide $s*k$, i.e. $\frac{s*k}{n}$ must be an integer. For this fraction to result in the smallest possible integer (since dealing with cyclic groups), divide both numerator and denumerator with $d=gcd(n,s)$. So we get,
\[
\frac{s*k}{n}=\frac{(\frac{s}{d})*k}{(\frac{n}{d})}
\]
By division theorem, we know $\frac{s}{d}$ and $\frac{n}{d}$ are co-prime. Therefore, $\frac{n}{d}$ must divide $k$ and precisely be equal in order to obtain the smallest fraction.    
\end{proof}

An important implication of this theorem is that for any element $a^{s}$ in $<a>$, the cyclic subgroup containing $a^{s}$ is generated by $a^{gcd(n,s)}$, where $n=|<a>|$.  

\begin{eg}
Let $G=\mathbb{Z}_{6}=\{0,1,2,3,4,5\}$ be a group of order $6$ under modulo $6$ addition. Clearly $1$ is a generator for the group, and so has order $6$, the same as the order of the group. Another generator for the group is $5$ since $gcd(5,6)=1=gcd(1,6)$ and so $<1>=<5>$ under module $6$ addition. Furthermore, a subgroup of order $3$ of $G$ is $H=\{0,2,4\}$. And a set $\{0,1\}$ for example is not a subgroup (why?).\\
\end{eg}

The following theorem puts together the main ideas with cyclic groups which form a significant type of groups.

\begin{Thrm}[Fundamental Theorem of Cyclic Groups]
Every subgroup of a cyclic group is cyclic. Moreover, if $|<a>|=n$, then the order of any subgroup of $<a>$ is a divisor of $n$. For each positive divisor $k$ of $n$, the group $<a>$ has a unique subgroup of order $k$ - namely $<a^{\frac{n}{k}}>$.
\end{Thrm}

A convenient way to deal with groups of finite order is using a {\bf group table} or {\bf Cayley Table}. Group tables are useful in particular when dealing with permutation groups which will be introduced later. For example, the group $\{0,1\}$ under modulo two addition has the following group table:\\

% group table for ({0,1},+)
\begin{center}
\begin{tabular}{c | c | c}
		& $e=0$ 	& $1$ \\ \hline
$e=0$	& $e$ 		& $1$\\  \hline
$1$		& $1$ 		& $e$ \\
\end{tabular}
\end{center}

\begin{Def}
Let $H < G$. A {\bf left co-set} $K$ of $H$ is defined as
$K=aH=\{x=ay;y \in H$ and $a \in G\}$
\end{Def}

A right co-set is defined in a similar manner as $K=Ha$. Note that co-sets can be defined using the concept of equivalence relations as well. $K$ as defined above is the equivalence class containing $a$ under the following relation:
\[
K=<a>=\{x;xa^{-1} \in K\}
\]

It is apparent that the size of a co-set of a subgroup is the same as the size of the subgroup itself since in essence the co-set is obtained by "multiplying" all the elements of the subgroup by another fixed element.

\begin{Thrm}
Two co-sets with non-empty intersection are equal.\\
\end{Thrm}
\begin{proof}
Let $K_{1}=aH$ and $K_{2}=bH$ be two co-sets of $H < G$ where $a,b \in G$. If $z \in  K_{1} \cap K_{2}$ we have, \\ 
\[
ah_{1}=bh_{2} \Rightarrow ah_{1}(h_{2})^{-1}=b \Rightarrow ah_{3}=b
\]
for some $h_{1},h_{2},h_{3} \in H$. We can write\\
\[
K_{2}=bH=ah_{3}H=aH=K_{1}
\]
\end{proof}

Based on this theorem, it can be observed that a subgroup $H$ of a group $G$ can be used to partition $G$ into disjoint co-sets of the same size. The number of co-sets generated is called the {\bf index} of $H$ and is denoted by $(G:H)$. We are now prepared to prove the important theorem of Lagrange.

\begin{Thrm}[Lagrange's Theorem]
The order of any subgroup divides the order of the group.\\
\end{Thrm}
\begin{proof}
Based on the above analysis, if $H < G$, then $O(G)=O(H)*(G:H)$!\\
\end{proof}

\begin{Thrm}
A group of prime order is cyclic.
\end{Thrm}
\begin{proof}
Let $a \in G$, where $|G|$ is a prime number, and let $H \leq G$ containing $a$ and its powers. This implies that $2 \leq |H| \leq |G|$. Since $|H|$ must divide $|G|$ by Lagrange's theorem and $G$ is of a prime order, therefore $H=G$. 
\end{proof}

\begin{Def}
A subgroup $H$ of a group $G$ is {\bf normal} if its left and right co-sets are the same, $aH=Ha$ for some $a \in G$
\end{Def}

Note that this definition does not imply that $ah=ha$ for some $h \in H$, but $ah_{1}=h_{2}a$ where $h_{1},h_{2} \in H$. By multiplying both sides by inverse of $a$ we get $ah_{1}(a)^{-1}=h_{2}$. The latter result is called the {\bf conjugate} and means that a subgroup is normal if it is closed under conjugation. It is obvious that any abelian subgroup is also normal.\\

Groups can be in general mapped to each other. An interesting class of groups called permutation group is a special case of a mapping. A mapping is much like a function operating on group elements.

\begin{Def} 
A mapping is called {\bf surjective} or {\bf onto} if for every element in the co-domain there exists an element in the domain under the mapping.
\end{Def}

\begin{Def}
A mapping is called {\bf injective} or {\bf one-to-one} if an element in the domain maps to one and only one element in the co-domain.
\end{Def}

A mapping that is both onto and one-to-one is called a {\bf bijection}.

\begin{Def}
A mapping $\theta$ from $(G,.)$ to $(H,*)$ is called a {\bf homomorphism} if for every $a,b \in G$ we have,\\
\[
\theta(a.b)=\theta(a)*\theta(b)
\]
\end{Def}

\begin{Def}
A homomorphism is called an {\bf isomorphism} if the mapping is one-to-one.
\end{Def}

\begin{Thrm}
Under a homomorphic mapping, the identity element is consistent.\\
\end{Thrm}
\begin{proof}
Let $\theta: G \rightarrow H$, and $e$ the identity in $G$. For $a \in G$ we have,\\
\[
\theta(e)=\theta(e.e)=\theta(e)\theta(e)
\]
multiplying both sides with inverse of $\theta(e)$ shows that $\theta(e)$ is indeed the identity in $H$.\\
\end{proof}

\begin{Thrm}
Under a homomorphic mapping, inverse of an element is consistent.\\
\end{Thrm}
\begin{proof}
Let $\theta: G \rightarrow H$ be a homomorphism and let $a \in G$. It can be written that,\\
\[
\theta(e)=\theta(aa^{-1})=\theta(a)\theta(a^{-1})=e
\]
\end{proof}

\begin{Thrm}
The image of a homomorphic mapping on an abelian group is abelian itself.\\
\end{Thrm}
\begin{proof}
Let $\theta: G \rightarrow H$ where $G$ is abelian. Let $a,b \in G$. We have,\\
\[
\theta(a)\theta(b)=\theta(ab)=\theta(ba)=\theta(b)\theta(a)
\]
\end{proof}

\begin{eg}
Let $G=(\{0,1,2,3\},+_{4})$ and $H=(\{1,-1,i,-i\},*)$ be two groups over integers and complex numbers respectively. An isomorphism can be defined from $G$ to $H$ as follows:\\
\[
\theta(0)=1,\theta(1)=i,\theta(2)=-1,\theta(3)=-i
\]
Note that $O(0)=O(1)=1,O(1)=O(i)=4,O(2)=O(-1)=2,O(3)=O(-i)=4$\\
\end{eg}

\begin{Def}
The {\bf kernel} of a homomorphism $\theta : G \rightarrow H$ is the set of elements in $G$ that map to the identity in $H$. 
\end{Def}

\begin{Thrm}
The kernel of a homomorphism $\theta : G \rightarrow H$ is a normal subgroup of $G$.
\end{Thrm}
\begin{proof}
Let $ker(\theta)=\{x \in G;\theta(x)=e_{H}\}$. First using the subgroup test we show that the kernel is a subgroup. Let $a,b \in ker(\theta)$, we have:
\[
\theta(ab^{-1})=\theta(a)\theta(b^{-1})=\theta(a)(\theta(b))^{-1}=e
\] 
To show the normal property, we use closure under conjugation for some $g \in G$ and $a \in ker(\theta)$:
\[
\theta(gag^{-1})=\theta(g)\theta(a)\theta(g^{-1})=\theta(g)e(\theta(g))^{-1}=\theta(g)(\theta(g))^{-1}=e
\]
\end{proof}

\begin{Thrm}
A homomorphism $\phi$ is one-to-one if $ker \phi = 	\emptyset$
\end{Thrm}
\begin{proof}
We need to show that 
\[
\phi(a)=\phi(b) \Rightarrow a=b
\]
We have
\[
\phi(a)=\phi(b) \Rightarrow \phi(a)(\phi(b))^{-1}=\phi(a)\phi(b^{-1})=\phi(ab^{-1})=e
\]
Where the right hand side is obtained by multiplying both sides by the inverse. By the hypothesis then we have:
\[
\phi(ab^{-1})=e \Rightarrow ab^{-1}=e \Rightarrow a=b
\]
\end{proof}

\begin{Thrm}
Let $\phi : G \rightarrow G'$ be a homomorphism with kernel $H$. The set of all the co-sets of $H$ under operation $(aH)(bH)=(ab)H$ forms a group called a {\bf factor group} or a {\bf quotient group} denoted by $G/H$.
\end{Thrm}

More generally, for any normal subgroup $H$, the set of all the co-sets forms a factor group. 

\begin{eg}
Let $\phi : \mathbb{Z} \rightarrow \mathbb{Z}^{3}$. Under this homomorphism, $H=3 \mathbb{Z} = \{...,-3,0,3,...\}$ and the co-sets will be:
\[
1H=\{...,-2,1,4,...\}
\]
\[
2H=\{...,-1,2,5,...\}
\]
Note that all the properties examined so far hold: the co-sets are disjoint, $H$ is the kernel and normal, etc. Also note that, letting $H=0H$, $(0H)(1H)=(1H)$, $(0H)(2H)=(2H)$, $(1H)(2H)=(0H)$ which verify a factor group is a group.  
\end{eg}

\begin{Thrm}[The Fundamental Homomorphism Theorem]
Let $\theta: G \rightarrow \theta(G)$ be a homomorphism with kernel $H$. The factor group of $H$ is isomorphic to $\theta(G)$.
\end{Thrm}

\begin{Def}
A one-to-one mapping of a group $G$ onto itself is a {\bf permutation}, i.e. $\theta: G \rightarrow G$.
\end{Def}

It can be shown that the number of permutations on a group of order $n$ is $n!$. Two permutations can follow each other resulting in a {\bf composition} of permutations. It will be shown that in fact a new group can be defined with composite permutation as the binary operations. A convenient way to deal with permutations is the cyclic notation shown in the following example. 

\begin{eg}
There are $6$ possible permutations on $\mathbb{Z}^{3}$ as follows:

\begin{displaymath}
e = (1)(2)(3) =
\left(
\begin{array}{rrr}
1 & 2 & 3\\
1 & 2 & 3
\end{array}
\right)
\end{displaymath}
 
\begin{displaymath}
\alpha = (12)(3) =
\left(
\begin{array}{rrr}
1 & 2 & 3\\
2 & 1 & 3
\end{array}
\right)
\end{displaymath}

\begin{displaymath}
\beta = (123) =
\left(
\begin{array}{rrr}
1 & 2 & 3\\
2 & 3 & 1
\end{array}
\right)
\end{displaymath}

\begin{displaymath}
\alpha \beta = (1)(23) =
\left(
\begin{array}{rrr}
1 & 2 & 3\\
1 & 3 & 2
\end{array}
\right)
\end{displaymath}

\begin{displaymath}
\beta^{2} = (132) =
\left(
\begin{array}{rrr}
1 & 2 & 3\\
3 & 1 & 2
\end{array}
\right)
\end{displaymath}

\begin{displaymath}
\alpha \beta^{2} = (13)(2) =
\left(
\begin{array}{rrr}
1 & 2 & 3\\
3 & 2 & 1
\end{array}
\right)
\end{displaymath}

and the group table using composition of two permutations becomes:

\begin{center}
\begin{tabular}{c | c c c c c c}
 & $e$ & $\beta$ & $\beta^{2}$  & $\alpha$ & $\alpha \beta$  & $\alpha \beta^{2}$ \\ \hline
$e$ &$e$ & $\beta$ & $\beta^{2}$ &$\alpha$ & $\alpha \beta$ &$\alpha \beta^{2}$\\
 $\beta$ &$\beta$ & $\beta^{2}$ & $e$& $\alpha \beta^{2}$&$\alpha$ & $\alpha \beta$ \\
  $\beta^{2}$ & $\beta^{2}$& $e$ & $\beta$& $\alpha \beta$ & $\alpha \beta^{2}$&$\alpha$\\
 $\alpha$   &$\alpha$ & $\alpha \beta$  & $\alpha \beta^{2}$& $e$&$\beta$ &$\beta^{2}$\\
   $\alpha \beta$   & $\alpha \beta$ & $\alpha \beta^{2}$ &$\alpha$ & $\beta^{2}$&$e$ &$\beta$\\
   $\alpha \beta^{2}$   & $\alpha \beta^{2}$ & $\alpha$ & $\alpha \beta$ & $\beta$& $\beta^{2}$&$e$\\
\end{tabular}
\end{center}

\end{eg}

The notation used in the previous example is known as the cyclic notation. For instance, $\beta^{2} = (132)$ indicates that under this permutation $1$ maps to $3$, $3$ to $2$, and $2$ to $1$. 

\begin{Thrm}
The set of all the permutations of a group under the binary operation of composition forms a group.  
\end{Thrm}
\begin{proof}
The identity is the permutation that maps each element to itself. Since any permutation is one-to-one, there exists an inverse for each. The associativity follows from the properties of composite operations. 
\end{proof}

\begin{Def}
The group of all permutations of $\{1,...,n\}$ is called the {\bf symmetric group} on $n$ letters denoted by $S_{n}$.
\end{Def}
  
\begin{Thrm}
Every permutation can be written as a composition of disjoint cycles.
\end{Thrm}

Note that under composition, permutations are not in general commutative. The concept of disjoint cycles provides a way to deal with such cases.

\begin{Thrm}
Disjoint cycles are commutative.
\end{Thrm}

\begin{Def}
A cycle of length $2$ is called a \bf{transposition}.
\end{Def}

\begin{Thrm}
A permutation can be written as a composition of only an even number of transpositions or an odd number of transpositions. 
\end{Thrm}
\begin{proof}
A permutation $\alpha$ on a set $A$ can be represented by a matrix multiplication. For instance if $\alpha(a)=b$ where $a$ and $b$ are an arrangement of the $n$ elements of $A$, then:
\[
\exists M_{nxn} \rightarrow Ma=b
\] 
where rows of $M$ are identity vectors (i.e. a single one and zeros) and the identity permutation is induced by the identity matrix $M=I_{nxn}$. Now, every transposition corresponds to a row operation, namely swapping of two rows. Given that a single row swap will result in a negative sign in the value of the determinant of $M$ which is either $-1$ or $1$, it can be seen that since the determinant is unique, either an even number of transpositions or an odd number of transpositions can be performed to induce $M$ from $I_{nxn}$. 
\end{proof}

\begin{Def}
The set of even permutations in a symmetric group $S_{n}$ forms a subgroup of the symmetric group called {\bf alternating group} and denoted by $A_{n}$.
\end{Def}

In what follows an important class of groups is introduced that comes handy in the study of rings, fields, polynomials, chinese remainder, and vector spaces.

\begin{Def}
A {\bf Direct Product} set is defined as $ \prod_{i=1}^{n} S_{i} = S_{1} \times S_{2} \times \dots \times S_{n}$, where $S_{i}'s$ are sets. Then this direct product is an n-tuple $(a_{1},a_{2},\dots,a_{n})$ with $a_{i} \in S_{i}$.    
\end{Def}     

\begin{Thrm}
The direct product of $n$ groups is a group under the following operation:
\[
(a_{1},a_{1},\dots,a_{n})(b_{1},b_{1},\dots,b_{n})=(a_{1}b_{1},a_{1}b_{1},\dots,a_{n}b_{n})
\] 
where $a_{i},b_{i} \in G_{i}$ for some group $G_{i}$.
\end{Thrm}

\begin{Thrm}
The direct product $\mathbb{Z}_{m} \times \mathbb{Z}_{n}$ is cyclic iff $gcd(m,n)=1$.
\end{Thrm}

\begin{Thrm} [the Theorem of Finitely Generated Abelian Groups]
Every Finitely Generated Abelian Group is isomorphic to a direct product of cyclic groups of a prime-power order in the form:
\[
\mathbb{Z}_{(p_{1})^{r_{1}}} \times \mathbb{Z}_{(p_{2})^{r_{2}}} \times \dots \times \mathbb{Z}_{(p_{n})^{r_{n}}}
\]
\end{Thrm}




 
